I don't know what your chances are with PayPal since they aren't really known for having great customer service, but if he misrepresented the condition of the vehicle he isn't entitled to one penny. Hell, he should be paying you back for your plane tickets!
Did you PayPal from your checking account or from a credit card? If it's a card you can contest it with your credit card company - they are much more responsive than PayPal.